Navigation devices are known which perform functions such as route searches between two locations. Modern navigation devices also may provide additional functionalities, such as serving as a travel guide that outputs, upon demand, information on points of interest (POI). Such information may include names of streets or POIs, but may also include additional textual or multimedia information. For illustration, some navigation devices may include travel guide functions to output detailed explanations, in textual and/or multimedia form, on objects, in response to receiving a name input.
In order to aid a user in inputting names, navigation devices may be configured to provide information on all potential next valid characters. This reduces or eliminates the risk that the user inputs a name which is not regarded valid by the navigation device. For illustration, by providing information on next valid characters and/or by limiting possible character inputs based on information on next valid characters, the inputting of a destination city or destination street may be prevented if the navigation device does not store information on the location of the respective city or street.
Information on next valid characters should desirably be provided without substantial delays, i.e., while the user is still in the process of inputting a name. In order to allow information on next valid characters to be retrieved quickly, dedicated search structures may be used. Such search structures may be specific search trees, which are also referred to as next valid character (NVC) trees. NVC trees may be used for different search paths. For illustration, there may be a NVC tree for valid city names in one country, such as Germany, and another NVC tree for valid city names in another country. There may be a NVC tree for valid road names in one city, and another NVC tree for valid road names in other cities. Leafs of the NVC tree may point to data base objects, for example. Alternatively, leafs of the NVC trees may also merely indicate that there are no valid names which include more characters, or may point to other data structures. For illustration, a leaf of NVC tree which indicates next valid characters for country names may point to a root node of another NVC tree which stores next valid characters for all cities in the respective country, or similar.
When a large number of possible names must be accommodated, storage space requirements for storing the various NVC trees may be significant. The addition of ever more functionalities, such as travel guide functionalities, which may also call for a verification of the validity of name input during the ongoing inputting of characters, may further increase such storage space requirements.